Read the original article here.

---

Okay, let's delve into the mechanics of interpreter execution, specifically a technique rarely exposed to the casual coder: Indirect Threading. Welcome to the engine room.

---

Underground Interpreter Engineering: Decoding Indirect Threading

High-level programming abstracts away the messy details of machine execution. You write code, a compiler or interpreter processes it, and magic seems to happen. But beneath the surface lies complex machinery. If you're learning "The Forbidden Code," you understand that true power comes from understanding the plumbing – the low-level techniques that make software run.

One such technique, crucial in the design of many virtual machines and interpreters, is threading. It's not about parallel execution; it's about how the interpreter figures out which piece of code to run next after executing the current instruction. Mastering this is mastering the heart of an execution environment.

We've discussed simpler methods like Token Threading and Direct Threading. Now, let's explore a more sophisticated, flexible, and sometimes faster technique: Indirect Threading.

The Interpreter's Core Loop: A Recap

Before we dissect Indirect Threading, let's quickly revisit the fundamental cycle of an interpreter.

Interpreter: A program that directly executes instructions written in a programming or scripting language, without requiring them to be previously compiled into a machine-code program.

Bytecode: A form of instruction set designed for efficient execution by a software interpreter. It's often an intermediate representation, higher-level than machine code but lower-level than source code, allowing for portability across different hardware architectures.

The typical interpreter works by repeatedly executing a sequence of operations for each instruction in the program's bytecode:

1. Fetch: Read the next instruction (or instruction identifier) from the bytecode stream.
2. Decode: Determine what operation the instruction represents.
3. Execute: Perform the action associated with the instruction (e.g., add two numbers, jump to a different part of the code).
4. Dispatch: Determine the location of the next instruction and jump to the start of the Fetch phase for it.

This Dispatch phase is where threading techniques come into play. How does the interpreter efficiently move from executing instruction N to instruction N+1?

Threading: The Art of the Jump

Threading techniques optimize the Dispatch phase. Instead of going back to a central loop's Fetch/Decode step every time, the execution of one instruction leads directly to the execution of the next. The handlers for each instruction are "threaded" together.

Common threading techniques include:

• Token Threading: The bytecode contains simple IDs (tokens) for instructions. The dispatch loop uses a large switch statement or a lookup table to find the handler code for the token ID. Simple but slow due to the central lookup overhead per instruction.
• Direct Threading: The bytecode contains the direct memory address of the handler code for each instruction. The dispatch is a simple goto *instruction_pointer++ (or equivalent). Much faster than token threading as it avoids the lookup, but less flexible.
• Subroutine Threading: Each instruction handler is a subroutine. The dispatch mechanism is essentially a sequence of subroutine calls. Handlers return to the instruction pointer after execution. Uses the native call stack, which can have overhead.

Now, let's introduce the subject of this chapter: Indirect Threading.

Indirect Threading: The Double Indirection

Indirect Threading adds a layer of separation between the bytecode and the instruction handlers. It uses a technique known as double indirection.

Indirect Threading: An interpreter dispatch technique where the bytecode stream contains a sequence of memory addresses. Each address points to an entry in a central dispatch table. Each entry in the dispatch table, in turn, contains the memory address of the actual code that implements the instruction.

Think of it like this:

1. The bytecode isn't a list of instructions or even handler addresses. It's a list of addresses of pointers.
2. These addresses point into a special table – the dispatch table.
3. The entries in the dispatch table are the actual pointers to the instruction handler code.
4. To execute an instruction, the interpreter follows two pointers: first from the bytecode to the dispatch table entry, and then from the dispatch table entry to the handler code.

Conceptual Flow:

Instruction Pointer (IP) points into the Bytecode Stream

Bytecode Stream:
+---------------------+
| Address of Table Entry A | --> [Table Entry A] --> Address of Handler Code 1
+---------------------+
| Address of Table Entry B | --> [Table Entry B] --> Address of Handler Code 2
+---------------------+
| Address of Table Entry C | --> [Table Entry C] --> Address of Handler Code 3
+---------------------+
...

Dispatch Table:
+-------------------+    +-----------------------+
| Table Entry A (Address) | --> | Address of Handler Code 1 |
+-------------------+    +-----------------------+
| Table Entry B (Address) | --> | Address of Handler Code 2 |
+-------------------+    +-----------------------+
| Table Entry C (Address) | --> | Address of Handler Code 3 |
+-------------------+    +-----------------------+
...

Instruction Handler Code:
+-----------------------+
| Handler Code 1        | (Implements Instruction A)
|  ...                 |
|  goto **IP; // Jump   | (Continues threading)
+-----------------------+

+-----------------------+
| Handler Code 2        | (Implements Instruction B)
|  ...                 |
|  goto **IP; // Jump   | (Continues threading)
+-----------------------+
...

The instruction pointer (IP) steps through the bytecode stream, which is just a sequence of addresses. For each address A in the bytecode, the interpreter fetches the value at A (which is the address B of a dispatch table entry), then fetches the value at B (which is the address C of the handler code), and finally jumps to C.

Once the handler code at C finishes its specific task, it doesn't return to a central loop. Instead, it calculates the address of the next instruction's table entry address in the bytecode (usually just IP++) and performs the same double-indirect jump goto **IP to the next handler. The handlers are the dispatch mechanism.

Pseudo-Code Implementation Snippet (Using GCC's computed goto extension):

// Assuming:
// void* bytecode[] - array of void pointers, each pointing to a dispatch table entry
// void* dispatch_table[] - array of void pointers, each pointing to an instruction handler
// void** ip - a pointer to the current position in the bytecode array

// Example Handlers (simplified)
// handler_add: { execute ADD; ip++; goto **ip; }
// handler_sub: { execute SUB; ip++; goto **ip; }
// handler_mul: { execute MUL; ip++; goto **ip; }

// Initial setup:
// ip points to the beginning of the bytecode array
// bytecode[0] might hold &dispatch_table[ADD_OPCODE]
// bytecode[1] might hold &dispatch_table[SUB_OPCODE]
// ... and so on, mapping instruction stream to table entries

void execute(void** bytecode_start) {
    void** ip = bytecode_start;
    goto **ip; // Start the first instruction dispatch

    // Handlers would be defined here or linked in

    // Example Handler fragment:
    // handler_add:
    //    // Perform addition operation using operand(s) near IP
    //    // (Operand handling makes this more complex in reality)
    //    // ... your instruction logic here ...
    //    ip++; // Move to the next instruction address in bytecode
    //    goto **ip; // Indirectly jump to the next handler
    //
    // handler_sub:
    //    // Perform subtraction operation
    //    // ...
    //    ip++;
    //    goto **ip;
    //
    // // ... other handlers ...

    // Need an 'end' handler for program termination
    // handler_end:
    //    return; // Or exit the process
}

// The bytecode array would actually contain addresses of the dispatch table entries:
// void* my_bytecode[] = { &dispatch_table[ADD_OPCODE], &dispatch_table[SUB_OPCODE], ..., &dispatch_table[END_OPCODE] };
// void* dispatch_table[] = { [ADD_OPCODE] = &&handler_add, [SUB_OPCODE] = &&handler_sub, [END_OPCODE] = &&handler_end }; // Using label addresses

// execute(my_bytecode);

This structure is powerful. Notice that the central execute function is just an entry point. The actual flow of control happens via the goto **ip; statements within the handlers themselves.

Advantages of Indirect Threading

Why use this seemingly complicated double indirection?

1. Maximum Flexibility: This is the primary advantage. The dispatch table acts as a translation layer.

   • You can remap instruction opcodes without changing the bytecode itself. Want ADD (opcode 1) to now execute a slightly different handler? Just change the pointer in dispatch_table[1].
   • You can implement dynamic optimization or patching. At runtime, you could change a table entry to point to an optimized version of a handler, or even debugging code, without modifying the running bytecode stream. This is powerful for Just-In-Time (JIT) compilation or adaptive execution environments.
   • Adding new instructions or variants is easier.
   • Can simplify target-specific optimizations. The handlers in the dispatch table can be specifically tuned for the current hardware architecture, while the bytecode remains portable.

2. Easier State Management: Compared to Subroutine Threading, you don't rely on the native call stack for the instruction flow itself, giving you more control over the interpreter's state.

Disadvantages and Considerations

There's no free lunch in low-level programming.

1. Performance Overhead: The main drawback is the double memory indirection. Reading *ip followed by *(*ip) requires two memory accesses per instruction dispatch. This is generally slower than the single indirection of Direct Threading (goto *ip). On modern CPUs with deep pipelines and caches, the penalty might be significant due to potential cache misses and branch prediction failures at the final goto.
2. Increased Memory Usage: Requires both the bytecode stream and the dispatch table in memory.
3. Complexity: Requires careful management of memory pointers and understanding of how goto with computed addresses works (often a non-standard language extension like GCC's &&label syntax).

Use Cases: Where the Forbidden Code Lurks

Indirect Threading is found in environments where flexibility and dynamic behavior are crucial, or where specific architectural features make the indirection less penalizing (though less common on modern general-purpose CPUs compared to Direct Threading).

• Older/Simpler Virtual Machines: Some early VMs or specialized interpreters might use this technique.
• Forth Systems: The Forth programming language often utilizes threaded code implementations, and Indirect Threading is one approach used.
• Emulators: Emulating certain architectures or systems might benefit from the flexibility of easily swapping instruction implementations via a dispatch table.
• Systems Requiring Runtime Patching or Modification: Environments where code behavior needs to be altered on the fly, perhaps for security, debugging, or dynamic optimization, can leverage the dispatch table.

Indirect vs. Direct Threading: A Trade-off

The choice between Indirect and Direct Threading is a classic performance vs. flexibility trade-off:

Feature	Direct Threading	Indirect Threading
Bytecode Content	Addresses of handlers	Addresses of table entries
Dispatch	Single indirect jump (goto *ip)	Double indirect jump (goto **ip)
Indirections	1	2
Flexibility	Low (bytecode tightly coupled to handlers)	High (dispatch table allows remapping/patching)
Performance	Generally faster due to fewer indirections/memory reads	Generally slower due to extra indirection, potentially better cache if table is hot
Memory	Bytecode only (handlers separate)	Bytecode + Dispatch Table

Direct Threading is often the performance king when flexibility isn't paramount. Indirect Threading shines when you need that extra layer of control and the ability to dynamically change how instructions are dispatched.

Why Won't They Teach You This in School?

Formal computer science curricula often focus on high-level abstractions, algorithms, and standard programming practices. Deep dives into the implementation details of virtual machines and low-level interpreter design are typically reserved for advanced operating systems, compiler design, or architecture courses, if covered at all.

Indirect Threading specifically is:

• An implementation detail, not a high-level concept.
• Often relies on non-standard language extensions (like GCC's computed goto).
• Used in specialized contexts (VMs, emulators, niche languages).
• Involves careful management of memory layout and pointers, which many introductory courses shy away from beyond basic structures.
• Requires understanding CPU architecture nuances like caching and branch prediction to fully appreciate its performance characteristics.

It's "forbidden" because it's below the level of abstraction most programmers operate at daily. It's the domain of system builders, VM architects, and those who dare to peer into the engine's core.

Conclusion

Indirect Threading is a powerful, albeit complex, technique for implementing interpreter dispatch. By introducing a layer of indirection via a dispatch table, it provides significant flexibility for runtime modification and instruction remapping, trading off some performance compared to simpler direct methods due to the extra memory access per instruction. Understanding techniques like Indirect Threading lifts the veil on how execution environments are built, giving you insights into the trade-offs made at the lowest levels of software design – essential knowledge for anyone truly mastering "The Forbidden Code."